Remove Zero Sum Consecutive Nodes from Linked List

LeetCode 1267 | Difficulty: Medium

Medium

Problem Description

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

- The given linked list will contain between `1` and `1000` nodes.

- Each node in the linked list has `-1000 <= node.val <= 1000`.

Topics: Hash Table, Linked List

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 165 ms)

Metric	Value
Runtime	165 ms
Memory	36.4 MB
Date	2022-01-07

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveZeroSumSublists(ListNode head) {
        if(head == null) return null;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = head;
    int sum = 0;
    while(cur != null)
    {
        if(cur.val + sum ==0 ) dummy.next = cur.next;
        sum += cur.val;
        cur = cur.next;
    }
    if (dummy.next != null) dummy.next.next = RemoveZeroSumSublists(dummy.next.next);
    return dummy.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Convert the linked list into an array.

Hint 2: While you can find a non-empty subarray with sum = 0, erase it.

Hint 3: Convert the array into a linked list.